All Questions
Tagged with time-complexitycomputational-complexity
8 questions
0votes
1answer
47views
How to estimate Time vs Memory trade-off prior to modelling
It is often the case when the time vs memory trade-off is underestimated prior to using ML/DL for solving a particular task. Taking into account the type, size and format of the available data and ...
0votes
1answer
196views
Why is the time complexity of the Triplet Loss $O(N^3)$
The triplet loss function uses an anchor, positive, and negative examples. If $N$ are the number of examples in the training set with $C$ classes, then I think that the time complexity should be $O(...
- 103
1vote
1answer
4kviews
What is the time complexity for testing a stacked LSTM model?
In the data preparation phase, we have to divide the dataset into two parts: the training dataset and the test dataset. I have seen this post regarding the time complexity for training a model. ...
1vote
1answer
752views
What is the time complexity of the upsampling stage of the U-net?
I am trying to determine the complexity of the neural network we use. The neural network is a U-net generator with an input shape of NxN (not an image but image-like data) and output of the same shape....
- 153
1vote
1answer
11kviews
What is the computational complexity of the forward pass of a convolutional neural network?
How do I determine the computational complexity (big-O notation) of the forward pass of a convolutional neural network? Let's assume for simplicity that we use zero-padding such that the input size ...
- 19
3votes
2answers
6kviews
Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?
I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is $\mathcal{O}(b^m)$. While I am reading, at some points, I found ...
4votes
0answers
75views
Given an input $x \in R^{1\times d}$ and a network with $s$ hidden layers, is the time complexity of the forward pass $O(d^{2}s)$? [duplicate]
I have a neural network that takes as an input a vector of $x \in R^{1\times d}$ with $s$ hidden layers and each layer has $d$ neurons (including the output layer). If I understand correctly the ...
2votes
1answer
1kviews
Why is exact inference in a Bayesian network both NP-hard and P-hard?
I should show that exact inference in a Bayesian network (BN) is NP-hard and P-hard by using a 3-SAT problem. So, I did formulate a 3-SAT problem by defining 3-CNF: $$(x_1 \lor x_2) \land (\neg x_3 \...
- 433
